#include <bits/stdc++.h>
using namespace std;
const int maxn = 110000;

#define fir(a,b,c) for (int a=b;a<=c;a++)

int t[maxn],A[maxn],n,m,i,len,k;
char str1[maxn], str2[maxn];
void solve()
{
    k=0;
    len = strlen(str1);
    for(i=len; i>=0; i--) 
        t[len-i-1] = str1[i] -(str1[i]<58 ? 48: str1[i]<97 ? 55: 61);//开始转换成为十进制
    while(len)
    {
        for(i=len; i>=1; i--) 
        {
            t[i-1] +=t[i]%m*n;//开始计算,首先*n,为n进制,然后转移到m进制
            t[i] /= m;//当前数已经处理完了
        }
        A[k++] = t[0] % m;//直接加到答案数组中
        t[0] /=m;//当前数已经处理完了
        while(len>0&&!t[len-1])  //处理0的情况
            len--;
    }
    str2[k] =NULL;
    fir(i,0,k-1)
        str2[k-1-i] = A[i]+(A[i]<10 ? 48: A[i]<36 ? 55:61);//三目运算符,具体可以百度,这段代码的意思是,找这个数字对应的字母
}

int main()
{


    scanf("%d %d\n%s",&n,&m,str1);

    // cout << str1;
    solve();
    cout << str2;
    // printf("%s\n",str2);
    return 0;
}
